package kaiao.dynamic;

import java.util.Arrays;

public class 零钱兑换 {

	public static void main(String[] args) {
		coinChange(new int[1], 0);
	}

	/**
	 * 像是完全平方数的简化版
	 *
	 * 1.考虑上一个数与下一个数之间的关系
	 * 2.此处主要是跳过的结果集的比较 例如 1 = 1corn 2 = 1corn + 1corn 或 2corn
	 * 3.完全平方数其实相当于corn，只是把corn变成了数学概念的平方数
	 * 状态移动方程 dp[n] = min(dp[n - 1] + 1, dp[i - corn] + 1]
	 *
	 * @author kai.ao
	 * @since 2024/6/16
	 */
	public static int coinChange(int[] coins, int amount) {

		// 需要考虑最小硬币值
		Arrays.sort(coins);

		// 初始化小结果集可得知的结果
		int[] dp = new int[amount + 1];
		Arrays.fill(dp, Integer.MAX_VALUE - 1);
		dp[0] = 0;
		// 动态计算当前值
		for (int i = coins[0]; i < amount + 1; i++) {

			for (int coin : coins) {
				if (coin > i) {
					continue;
				}
				dp[i] = Math.min(dp[i], dp[i - coin] + 1);
			}
		}

		return dp[amount] == Integer.MAX_VALUE - 1 ? -1 : dp[amount];
	}
}
